/* 将两个递增有序表合并成一个递增有序表 */

#include <iostream>
#include "sqlist.cpp"
using namespace std;

// 合并
bool merge(Sqlist A, Sqlist B, Sqlist &C)
{
  // 3个指针，分别指向递增有序表ABC
  int i = 0, j = 0, k = 0;
  
  // AB两个顺序表都有剩余元素 -- 进行比较
  while (i < A.length && j < B.length)
  {
    // 哪个元素更小，就添加进C
    if (A.data[i] < B.data[j])
      C.data[k++] = A.data[i++];
    else
      C.data[k++] = B.data[j++];
  }
  
  // 只有A中有多余元素 -- 全部合并进C
  while (i < A.length)
    C.data[k++] = A.data[i++];
  
  // 只有B中有多余元素 -- 全部合并进C
  while (j < B.length)
    C.data[k++] = B.data[j++];
  
  // 更新长度
  C.length = k;
  
  // 合并成功
  return true;
}

int main()
{
  // 创建递增有序表
  Sqlist A = {{2, 5, 9, 13, 19}, 5};
  
  // 创建递增有序表
  Sqlist B = {{1, 6, 7, 10}, 4};
  
  // 初始化顺序表
  Sqlist C;
  
  // 合并
  merge(A, B, C);
  
  // 打印
  for (int j = 0; j < C.length; ++j)
    cout << C.data[j] << " ";
}